import java.util.Arrays;

public class HeapSort {
    //实现从小到大排序
    public static void heapsort(int[] array) {
        //构建一个大根堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
        //循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            downAdjust(array, 0, i);
        }
    }

    /**
     * 维护大根堆：当孩子节点大于父节点的值，与之交换
     * @param array  数组
     * @param parentIndex  父亲下标
     * @param length 数组长度
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        int temp = array[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < length) {
            if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            //当父节点大于孩子节点中的最大值
            if (temp >= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
        array[parentIndex] = temp;
    }


    public static void main(String[] args) {
        int[] array = new int[]{1,3,4,2,0,6,7,9,5,8};
        heapsort(array);
        System.out.println(Arrays.toString(array));
    }
}
